package main

import "fmt"

func main() {
	fmt.Printf("wordBreak(\"catsandog\", []string{\"cats\", \"dog\", \"sand\", \"and\", \"cat\"}): %v\n", wordBreak(
		"abcd", []string{"a", "abc", "b", "cd"}))
}

/**
思考：因为要全部字符串都要匹配，即从左往右，都要符合条件才行
那么就可以考虑从后往前查看
n := len(s)
s[n-1:n] 满足的话就看 s[n-2,n-1]满足不
不满足就看s[n-3:n-1]
即dp[i] 表示第i个字符到结尾是否满足，最后返回dp[0]
*/
func wordBreak(s string, wordDict []string) bool {
	dp := make([]bool, len(s))
	m := make(map[string]struct{}, len(wordDict))
	// 先把字典保存，方便查询
	for _, str := range wordDict {
		m[str] = struct{}{}
	}
	for i := len(s) - 1; i > -1; i-- {
		if _, ok := m[s[i:]]; ok {
			dp[i] = true
		} else {
			// 一般来说，会走下面的for
			for j := i + 1; j < len(s); j++ {
				// 把s[i:] 拆分成s[i:j] 和s[j:]
				// s[i:j] 如果满足那就看，s[j:]
				// 都满足时，dp[i] 就说明是true，就可以继续循环i了
				if _, ok := m[s[i:j]]; ok {
					dp[i] = dp[j]
				}
				if dp[i] {
					break
				}
			}
		}
	}
	return dp[0]
}
